package com.lyt.springboot.util.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class S18 {
   //hashmap方法：1q
    public int[] twoSum (int[] numbers, int target) {
        int[] arr = new int[0];
        HashMap<Integer,Integer> hash = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
           if(!hash.containsKey(target-numbers[i])) {
               hash.put(numbers[i],i);

           }else {
              return new int[]{hash.get(target - numbers[i])+1, i+1};

           }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
//        S18 s18 = new S18();
//        int[] ints = s18.twoSum(arr, 7);
//        for (int i = 0; i < arr.length; i++) {
//            if(i<3){
//                continue;
//
//            }
//            System.out.println(arr[i]);
//
//        }
        int d = 2<<3;
        System.out.println(d);

    }

    /**
     * 三数之和
     * @param num
     * @return
     */
    //双指针法！
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        //定义返回值2
        ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();
        //sort排序下 方便指针比较
        Arrays.sort(num);
        //长度
        int len = num.length;
        if (len < 3) {
            return arrayList;
        }
        //双指针遍历
        for (int i = 0; i < len - 2; i++) {
            if(i!=0 && num[i]==num[i-1]) {
                continue;
            }
            int left = i + 1;
            int right = len - 1;
            int target = -num[i];
            //两数之和  不用hash查询
            while (left < right) {
                //定义
                ArrayList<Integer> temp = new ArrayList<>();
                if (num[left] + num[right] == target) {
                    temp.add(num[i]);
                    temp.add(num[left]);
                    temp.add(num[right]);
                    arrayList.add(temp);
                    //查重
                    while (left + 1 < right  && num[left] == num[left + 1]) {
                        left++;
                    }
                    while (right - 1 > left && num[right - 1] == num[right]) {
                        right--;

                    }
                    left++;
                    right--;
                } else if (num[left] + num[right] < target) {
                    left++;

                } else if (num[left] + num[right] > target) {
                    right--;
                }


            }

        }
        return arrayList;
    }

}

